The present invention relates to method and apparatus for arithmetic division, and, in particular, to method and apparatus for performing arithmetic division in digital circuits.
Division is a time consuming arithmetic function performed by digital computers and digital circuits that require extensive circuitry. A dividend is divided by a divisor to obtain a quotient and a remainder, if any. In a first step, the divisor is subtracted from the initial dividend. Thereafter, in subsequent steps, a current dividend is obtained by shifting each bit of the previous dividend by one toward the next higher order bit of the previous dividend, leaving a vacant lowest order bit. Further, in each step, the divisor is subtracted from the higher order bits of the current dividend to obtain a partial remainder. The partial remainder and the vacant lower order bits of the initial dividend are concatenated. If the result of the subtraction is positive, then a xe2x80x9c1xe2x80x9d is recorded for that place of the quotient in the lowest order bit position, and a next shift and subtraction occur. If the result of the subtraction is negative, a xe2x80x9c0xe2x80x9d is recorded for the quotient in the lowest order bit position, and the dividend is restored to its previous condition by adding back the divisor before the next shift and subtraction. However, this process is very time consuming and requires extensive logic components for performing the above steps.
To alleviate such shortcomings, non-restoring techniques have been utilized. An N-bit dividend is divided by an N-bit divisor by performing N repeated subtractions between them by shifting registers. The dividend and the divisor are stored in corresponding registers, and a remainder register is initialized to zero. The divisor is subtracted from a number including the lower (Nxe2x88x921) bits of the remainder and the highest order bit of the dividend register. If the subtraction fails, a zero is stored into the lowest order bit position of the dividend register, and the dividend and the remainder registers are shifted one bit toward their highest order bit positions, such that the highest order bit of the dividend register is shifted out into the lowest order bit of the remainder register. If the subtraction is successful, a xe2x80x9c1xe2x80x9d is stored into the lowest order bit of the dividend register, and the dividend and the remainder registers are shifted one towards their highest order bits, and the results of the subtraction is written into the remainder register. Repeating the above subtraction by shifting steps N times provides the quotient of the division in the dividend register and the remainder of the division in the remainder register.
Although using the non-restoring method the number of steps for performing division is reduced, a logic circuit for dividing a dividend by a divisor according to such methods requires several hundred logic gates. This is because often a digital logic circuit must be designed to divide one number by another number, and the number of logic gates depends on the number of bits being divided. Such circuits are expensive to design and manufacture, consume precious circuit space, and require excessive power for operating and cooling purposes.
There is, therefore, a need for a method and apparatus which provides for dividing a dividend by a divisor using reduced circuit components and functional steps.
The present invention satisfies these needs. In one embodiment the present invention provides a method and apparatus for calculating a quotient from a dividend and a divisor. The dividend comprises an X-bit binary number divisible by the divisor without a remainder, wherein the divisor is represented as (2N+2M) where N is greater than M. According to an embodiment of the method of the present invention, the values of N and M are determined such that the divisor is equal to the value (2N+2M). Then, the M-th through the (Nxe2x88x921)-th bits of the dividend are selected as lower order bits of the quotient. To obtain the higher order bits of the quotient, the (Nxe2x88x921)-th and the (2Nxe2x88x92Mxe2x88x921)-th bits of the dividend are examined. If the (Nxe2x88x921)-th bit of the dividend is xe2x80x9c1xe2x80x9d and if the (2Nxe2x88x92Mxe2x88x921)-th bit of the dividend is xe2x80x9c0xe2x80x9d, then the value xe2x80x9c1xe2x80x9d is subtracted from a value represented by the (2Nxe2x88x92M)-th through the (Xxe2x88x921)-th bits of the dividend to obtain a value representing the higher order bits of the quotient. Otherwise, the (2Nxe2x88x92M)-th through the (Xxe2x88x921)-th bits of the dividend are selected as higher order bits of the quotient. Finally, the higher order bits and the lower order bits are concatenated to obtain the quotient.
In an example of the method of the present invention, the dividend is stored in a dividend register having at least X bits, such that the 0-th through the (Xxe2x88x921)-th bits of the dividend are stored into the 0-th through the (Xxe2x88x921)-th bits of the dividend register, respectively. The M-th through the (Nxe2x88x921)-th bits of the dividend register are stored into the 0-th through the (Nxe2x88x92Mxe2x88x921)-th bits of the quotient register, respectively, in parallel or by shifting. If the (Nxe2x88x921)-th bit of the dividend register is xe2x80x9c1xe2x80x9d and if the (2Nxe2x88x92Mxe2x88x921)-th bit of the dividend is xe2x80x9c0xe2x80x9d, then the value xe2x80x9c1xe2x80x9d is subtracted from a value represented by the (2Nxe2x88x92M)-th through the (Xxe2x88x921)-th bits of the dividend register, and the result of the subtraction is stored in the (Nxe2x88x92M)-th through the (2Nxe2x88x922Mxe2x88x923)-th bits of the quotient register, in parallel or by shifting. Otherwise, the (2Nxe2x88x92M)-th through the (Xxe2x88x921)-th bits of the dividend register are stored into the (Nxe2x88x92M)-th through the (2Nxe2x88x922Mxe2x88x923)-th bits of the quotient register, respectively, in parallel or by shifting. The quotient is represented by the 0-th through the (2Nxe2x88x922Mxe2x88x923)-th bits of the quotient register.
In another aspect, the present invention provides a digital division circuit for performing said division, wherein the dividend is stored in a dividend register. In one embodiment, the digital division circuit comprises: (a) a first circuit connected to the dividend register for providing the M-th through the (Nxe2x88x921)-th bits of the dividend as lower order bits of the quotient; (b) a second circuit connected to the dividend register for providing the (2Nxe2x88x92M)-th through the (Xxe2x88x921)-th bits of the dividend as a first higher order bit segment for the quotient; (c) a detector connected to the dividend register for detecting the (Nxe2x88x921)-th and the (2Nxe2x88x92Mxe2x88x921)-th bits of the dividend and for generating a control signal if: (1) the (Nxe2x88x921)-th bit of the dividend is xe2x80x9c1xe2x80x9d and (2) if the (2Nxe2x88x92Mxe2x88x921)-th bit of the dividend is xe2x80x9c0xe2x80x9d; (d) a subtractor connected to the second circuit for subtracting the value xe2x80x9c1xe2x80x9d from data including the (2Nxe2x88x92M)-th through the (Xxe2x88x921)-th bits of the dividend and generating output bits as a second higher order bit segment for the quotient; and (e) a selector connected to the second circuit and to the subtractor, and responsive to the control signal from the detector for selecting between the first and second higher order bit segments to provide higher order bits of the quotient, wherein: (1) in the presence of the control signal the selector provides said second higher order bit segment as the higher order bits of the quotient, otherwise, (2) in the absence of the control signal the selector provides said first higher order bit segment as the higher order bits of the quotient. The higher and lower order bits represent a value of the quotient. The digital division circuit can further comprise a quotient register for storing the quotient therein. The first circuit is connected to the dividend register and to the quotient register for storing the M-th through the (Nxe2x88x921)-th bits of the dividend register into the 0-th through (Nxe2x88x92Mxe2x88x921)-th bits of the quotient register, respectively, as the lower order bits of the quotient. Further, the selector can comprise a multiplexer connected: (1) to the second circuit and to the subtractor, and (2) to the quotient register, for storing the second higher order bit segment into the (Nxe2x88x92M)-th through the (2Nxe2x88x922Mxe2x88x923)-th bits of the quotient register as the higher order bits of the quotient in response to the control signal from the detector, and for storing the first higher order bit segment into the (Nxe2x88x92M)-th through the (2Nxe2x88x922Mxe2x88x923)-th bits of the quotient register, respectively, as the higher order bits of the quotient in the absence of the control signal from the detector. As such, the quotient is represented by data including the 0-th through the (2Nxe2x88x922Mxe2x88x923)-th bits of the quotient register.
Therefore, a division circuit according to the present invention is more efficient and requires substantially fewer logic gates and operation functions than conventional division circuits for calculating a quotient from a dividend and a divisor as defined above.